package com.zwj.interview.二分查找;

/**
 * 输入一个排序的整数数组nums和一个目标值t，如果数组nums中包含t，则返回t在数组中的下标；如果数组nums中不包含t，
 * 则返回将t按顺序插入数组nums中的下标。假设数组中没有相同的数字。
 * 例如，输入数组nums为[1，3，6，8]，如果目标值t为3，则输出1；如果t为5，则返回2
 */
public class 寻找下一个可以插入元素的位置 {

    //下一个可以插入的位置有这样的特点：这个位置前的所有数字都小于它并且她小于这个位置后面的每一个数
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            //找到可以插入的位置
            if (nums[mid] >= target) {
                /**
                 * 由于数组是排序的，因此它应该排在所有比它小的数字的后面。
                 * 也就是说，它的插入位置满足两个条件：一是该位置上的数字大于t，二是该位置的前一个数字小于t。
                 * 例如，当数组为[1，3，6，8]，目标值为5时，它将被插入下标为2的位置，该位置当前的值为6，大于目标值，该位置的前一个值是3，小于目标值
                 */
                //前一个还大于目标值，mid==0说明数组第一个数就大于目标值，也就是说数组中所有数字
                //都大于target,那么插入位置就在数字第一个位置
                if (mid == 0 || nums[mid - 1] < target) {
                    return mid;
                }
                //到这是说明前面一个位置依然大于target，说明需要缩小范围
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        /**
         *
         *
         * 第2种情况是当数组中不存在大于或等于目标值t的数字时，
         * 那么t应该添加到数组所有值的后面，即返回数组的长度
         */
        return nums.length;
    }

    public int searchInsert2(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            //如果中间的值大于target,那么就要看其前一个位置跟target的大小
            if(nums[mid]>=target){
                if(mid==0 || nums[mid-1]<target){
                    return mid;
                }
                //走到这里，说明nums[mid-1]>target
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        //走到这里，说明要插入的数字大于数组中的所有数字，那么就插在最后
        return nums.length;
    }
}
